Various technologies have been proposed, which visualize a set of a plurality of elements while reflecting relationships between the elements, by using a computer. As this type of technology, there is a technology which graphically displays data including a plurality of data elements organized with a hierarchy structure (hereinafter, referred to as hierarchical data).
Conventionally, in the technology of graphically displaying this type of hierarchical data in real time, the hierarchy structure has been displayed, in general, by use of a tree structure. For example, Explorer, which is a file operating system running on Windows, the operating system by Microsoft Corporation, U.S., displays the hierarchy structure of a file system by using a simple tree structure, in which data elements are arranged in a row and arcs are placed between the data elements.
However, since this is a simple method of just arranging data elements in a row, in the case of graphically displaying large-scale hierarchical data including thousands to tens of thousands of data elements, it is difficult to display a large quantity of information on a screen.
As a method of displaying hierarchical data more suitable for large-scale data than Explorer, Treemap method and Hyperbolic Tree method are conceived.
The Treemap method expresses a hierarchy structure of data by splitting a screen space on which the hierarchical data is displayed in alternating vertical and horizontal directions and making the split regions correspond to individual data elements. This Treemap method is described in detail, for example, in the following literature 1.
literature 1: Shneiderman B., Tree visualization with treemaps: a 2-d space-filling approach, ACM Transactions on Graphics, vol. 11, 1 (January 1992), 92-99. or http://www.cs.umd.edu/hcil/treemaps/
In the Hyperbolic Tree method, a tree structure is arranged in a hyperbolic space. The following literature 2 discloses a method applying this Hyperbolic Tree method to express both a hierarchy structure and a link structure between data elements.
literature 2: Hao M. C., Hsu M., Dayal U., and Krug A., Web-based Visualization of Large Hierarchical Graphs Using Invisible Links in a Hyperbolic Space, HP Laboratories Palo Alto, HPL-2000-2.
FIG. 36 is a view showing an example of displaying hierarchical data using the technology disclosed in the literature 2.
Referring to FIG. 36, arcs are radially extended from the highest hierarchy level toward lower hierarchy levels. Individual data elements placed at the lowest hierarchy level are finally arranged at the outermost periphery.
Incidentally, as a method of visualizing a hierarchy structure of hierarchical data, a method is conceived, which combines regions (rectangular regions, for example) which are made to correspond to hierarchy levels, in a nested manner for a graphics display. Specifically, an individual region is set for each classification of data elements constituting the hierarchy structure, and the data elements are arranged in the regions.
In this case, if all the data elements arranged in a predetermined region are expressed by cells in the same shape and of the same size, the data elements can be arranged by just arraying the cells. However, when the meanings and contents of the data elements are reflected on the shapes and sizes of the cells, it becomes a problem how efficiently the cells are arranged in the region.
If the regions and the cells are expressed by rectangles, this problem comes to a problem that “a set composed of rectangles of arbitrary sizes is arranged in the minimum rectangular region.” This problem is called Packing, Nesting, Marking, or the like, and applied in fields of arranging VLSIs (Very Large Scale Integrated Circuit) on a board, arranging patterns of clothes, arranging mechanical parts on a plate, and the like. Various techniques have been presented to solve this problem in these fields.
As described above, the technique for expressing a hierarchy structure by use of a tree structure has hitherto been used as the technique for graphically displaying hierarchical data.
However, it has been difficult for the simple tree structure, in which data elements are arrayed in a row and arcs are placed between the data elements, to display all the data elements of large-scale hierarchical data on a screen.
The Treemap method disclosed in the literature 1 is a technique suitable for large-scale hierarchical data to graphically display hierarchical data in comparison with the above described simple tree structure. However, when thousands to tens of thousands of data elements are displayed, the regions of minimum units which are made to correspond to the data elements are excessively fine, and the visibility thereof is lowered.
Similarly, even in the technique disclosed in the literature 4 using the Hyperbolic Tree method, which is considered to be suitable for the graphics display of relatively large-scale hierarchical data, the individual data elements on the lowest hierarchy level are arranged in the periphery of a radial tree structure. Accordingly, it is difficult to display thousands to tens of thousands of data elements.
Furthermore, any of these technologies for graphically displaying hierarchical data using a tree structure expresses a hierarchy structure related to classification of data elements by use of the tree structure. Therefore, the hierarchy structure is easily recognized, but in the case where there is any relationship (link structure) between the individual data elements, it is difficult to display this link structure by means of placing arcs or the like.
Moreover, in the case of using the method of performing a graphics display with nested regions as a technique for visualizing the hierarchy structure of hierarchical data, as previously described, it is required to solve the problem that a set composed of cells of arbitrary sizes are arranged in a minimum region. There have already been various techniques for solving this problem. However, most thereof are optimization techniques for minimizing an arrangement region, in other words, technologies of “minimizing the arrangement region regardless of the length of calculation time (even with a long calculation time).”
However, when this problem is tried to be solved as part of the technology of graphically displaying hierarchical data, it is required to reduce the calculation time (for example, a few seconds, a time period to allow an interactive operation) and to obtain, even if not optimal, a proper arrangement result to a certain degree.
In this connection, an object of the present invention is to provide a technique for easily generating a graphics image of large-scale hierarchical data.
Another object of the present invention is to provide a technique for rapidly performing processing of efficiently arranging elements of arbitrary sizes in a predetermined region.